package day23;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 题目：计算字符串的编辑距离
 * 题目链接：https://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314?tpId=37&&tqId=21275&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking
 */
public class Main1 {
    public static int func(String A,String B) {
        int n = A.length();    //行
        int m = B.length();    //列
        int[][] dp = new int[n+1][m+1];
        for (int i = 0; i <= n; i++) {    //初始化第一列
            dp[i][0] = i;
        }
        for (int i = 0; i <= m; i++) {   //初始化第一行
            dp[0][i] = i;
        }
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m ; j++) {
                if(A.charAt(i-1) == B.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = reader.readLine()) != null) {
            String str = reader.readLine();
            System.out.println(func(line, str));
        }
    }
}
